/*
 * Antonio Canabrava Fraideinberze 7152292
 * Lucas Avelino Sodre Santos      7239086
 * Pedro Rael Garcia               7153021
 */

/*
 * Library used in programs that implements avl tree
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>


#include "avl.h"

/*
 *  clear an AVL tree
 */


int getSizeTree(node *t){
    if (t == NULL)
        return 0;
    else
      return 1 + getSizeTree(t->left) + getSizeTree(t->right);

}

void clear(node *t) {
    if (t != NULL) {
        clear(t->left);
        clear(t->right);
        free(t);
    }
}

/*
 *   find a specific node's key in the tree
 */
node *find(char *word, node *t) {
    if (t == NULL)
        return NULL;

    if (strcmp(word, t->word) < 0)
        return find(word, t->left);

    else if (strcmp(word, t->word) > 0)
        return find(word, t->right);

    else
        return t;
}

node *findSub(char *word, node *t, int i) {
    if (t == NULL)
        return NULL;

    if (strcmp(word, t->word) < 0)
        return findSub(word, t->left, i);

    else if (strcmp(word, t->word) > 0)
        return findSub(word, t->right, i);

    else {
        t->partition[i] = 1;
        t->blocks--;
        if(t->blocks == 0)
          t->complete = 1;

        return t;
    }
}

node *findN(char *word, node *t, int len) {
    if (t == NULL)
        return NULL;

    if (strncmp(word, t->word, len) < 0)
        return findN(word, t->left, len);

    else if (strncmp(word, t->word, len) > 0)
        return findN(word, t->right, len);

    else
        return t;
}

/*
 *  find minimum node's key
 */
node *find_min(node *t) {
    if (t == NULL)
        return NULL;

    else if (t->left == NULL)
        return t;

    else
        return find_min(t->left);
}

/*
 *  find maximum node's key
 */
node *find_max(node *t) {
    if (t != NULL)
        while (t->right != NULL)
            t = t->right;

    return t;
}

/*
 *  get the height of a node
 */
static int height(node *n) {
    if (n == NULL)
        return -1;

    else
        return n->height;
}

/*
 *  get maximum value of two integers
 */
static int max(int l, int r) {
    return l > r ? l : r;
}

/*
 *  perform a rotation between a k2 node and its left child
 *
 *  note: call single_rotate_with_left only if k2 node has a left child
 */
static node *single_rotate_with_left(node *k2) {
    node *k1 = NULL;
    k1 = k2->left;
    k2->left = k1->right;
    k1->right = k2;
    k2->height = max(height(k2->left), height(k2->right)) + 1;
    k1->height = max(height(k1->left), k2->height) + 1;
    return k1; /* new root */
}

/*
 *  perform a rotation between a node (k1) and its right child
 *
 *  note: call single_rotate_with_right only if
 *         the k1 node has a right child
 */
static node *single_rotate_with_right(node *k1) {
    node *k2;
    k2 = k1->right;
    k1->right = k2->left;
    k2->left = k1;
    k1->height = max(height(k1->left), height(k1->right)) + 1;
    k2->height = max(height(k2->right), k1->height) + 1;
    return k2; /* New root */
}

/*
 *
 *  perform the left-right double rotation,
 *
 *  note: call double_rotate_with_left only if k3 node has
 *         a left child and k3's left child has a right child
 */
static node *double_rotate_with_left(node *k3) {
    /* Rotate between k1 and k2 */
    k3->left = single_rotate_with_right(k3->left);
    /* Rotate between K3 and k2 */
    return single_rotate_with_left(k3);
}

/*
 *  perform the right-left double rotation
 *
 *  notes: call double_rotate_with_right only if k1 has a
 *          right child and k1's right child has a left child
 */
static node *double_rotate_with_right(node *k1) {
    /* rotate between K3 and k2 */
    k1->right = single_rotate_with_left(k1->right);
    /* rotate between k1 and k2 */
    return single_rotate_with_right(k1);
}

/*
 *  insert a new node into the tree
 */
node *insert(char *word, node *t) {
    float len;

    float temp = 0;

    if (t == NULL) {
        /* create and return a one-node tree */
        t = (node *) malloc(sizeof (node));

        if (t == NULL) {
            fprintf(stderr, "Out of memory!!! (insert)\n");
            exit(1);
        }
        else {
            len = strlen(word);
            t->word = (char *) malloc(len);
            strncpy(t->word, word, len);
            t->height = 0;
            t->complete = 0;
            t->size_word = (int) len;
            t->left = t->right = NULL;
            t->left = t->right = NULL;
            temp = ((len / 5 - (int) (len / 5)) > 0 ? (int) (len / 5 + 1) : (int) (len / 5));
            t->blocks = (int) temp;
            t->partition = (int*) calloc(t->blocks, sizeof (int));

        }
    }
    else if (strcmp(word, t->word) < 0) {
        t->left = insert(word, t->left);

        if (height(t->left) - height(t->right) == 2) {
            if (strcmp(word, t->left->word) < 0)
                t = single_rotate_with_left(t);

            else
                t = double_rotate_with_left(t);
        }
    }
    else if (strcmp(word, t->word) > 0) {
        t->right = insert(word, t->right);

        if (height(t->right) - height(t->left) == 2) {
            if (strcmp(word, t->right->word) > 0)
                t = single_rotate_with_right(t);

            else
                t = double_rotate_with_right(t);
        }
    }

    /* else X is in the tree already; we'll do nothing */
    t->height = max(height(t->left), height(t->right)) + 1;
    return t;
}

node *insertSub(char *word, char* wordComplete, node *t, int i) {
    float len;

    if (t == NULL) {
        /* create and return a one-node tree */
        t = (node *) malloc(sizeof (node));

        if (t == NULL) {
            fprintf(stderr, "Out of memory!!! (insert)\n");
            exit(1);
        }
        else {
            len = strlen(word);
            t->word = (char *) malloc(len);
            strncpy(t->word, word, len);
            t->height = 0;
            t->size_word = (int) len;
            t->left = t->right = NULL;

            t->blocks = i;
            initRow(&t->rowSub);
            insertRow(&t->rowSub, wordComplete);

        }
    }
    else if (strcmp(word, t->word) < 0) {
        t->left = insertSub(word, wordComplete, t->left, i);

        if (height(t->left) - height(t->right) == 2) {
            if (strcmp(word, t->left->word) < 0)
                t = single_rotate_with_left(t);

            else
                t = double_rotate_with_left(t);
        }
    }
    else if (strcmp(word, t->word) > 0) {
        t->right = insertSub(word, wordComplete, t->right, i);

        if (height(t->right) - height(t->left) == 2) {
            if (strcmp(word, t->right->word) > 0)
                t = single_rotate_with_right(t);

            else
                t = double_rotate_with_right(t);
        }
    } else {
        insertRow(&t->rowSub, wordComplete);
        //       printf("palavra de 5 %s, palavra completa %s, i %d\n",word,wordComplete,i);
        //       printRow(*t->rowSub);
        //       getchar();
    }

    /* else X is in the tree already; we'll do nothing */
    t->height = max(height(t->left), height(t->right)) + 1;

    return t;
}

/*
 *  data of a node
 */
char *get(node *n) {
    return n->word;
}

/*
 *  recursively display AVL tree or subtree
 */
void display_avl(node *t) {
    if (t == NULL)
        return;

    printf("%s ", t->word);

    if (t->left != NULL)
        printf("(L:%s)", t->left->word);

    if (t->right != NULL)
        printf("(R:%s)", t->right->word);

    printf("\n");
    display_avl(t->left);
    display_avl(t->right);
}
void display_avl_left(node *t) {
    if (t == NULL)
        return;
    if(t->complete == 0) {
      printf("%s ", t->word);

      if (t->left != NULL)
          printf("(L:%s)", t->left->word);

      if (t->right != NULL)
          printf("(R:%s)", t->right->word);

      printf("\n");
    }
    display_avl_left(t->left);
    display_avl_left(t->right);
}

void display_avl_row(node *t) {
//     printRow(*t->rowSub);
}

char* getRowNode(node* t) {
    return removeRow(&t->rowSub);
}

void display_avl_blocks(node *t){
  int i;

  for(i = 0; i < t->blocks; i++)
    printf("%d ",t->partition[i]);

  printf("\n");
}
